package com.example.mysql.学习笔记.高级.数据库的优化之索引.索引的数据结构.其他索引结构;

public class Hash结构 {
}

/**
 * 6.2 Hash结构   对于等值判断   效率极高  不能范围查找
 * Hash本身是一个函数，又被称为散列函数，它可以帮助我们大幅提升检索数据的效率。
 * Hash算法是通过某种确定性的算法(比如MD5、SHA1、SHA2、SHA3) 将输入转变为输出。
 * 相同的输入永远可以得到相同的输出，假设输入内容有微小偏差,在输出中通常会有不同的结果。
 * 举例:如果你想要验证两个文件是否相同，那么你不需要把两份文件直接拿来比对，
 * 只需要让对方把 Hash 函数计算得到的结果告诉你即可，
 * 然后在本地同样对文件进行Hash函数的运算，
 * 最后通过比较这两个Hash函数的结果是否相同，就可以知道这两个文件是否相同。
 *
 * 加速查找速度的数据结构，常见的有两类:
 * (1)树，例如平衡二叉搜索树，查询/插入修改/删除的平均时间复杂度都是0(log2N);
 * (2)哈希，例如HashMap, 查询/插入修改/删除的平均时间复杂度都是0(1);
 *
 *   哈希函数h有可能将两个不同的关键字映射到相同的位置，
 *   这叫做碰撞，在数据库中--般采用链接法来解决
 *
 */

/**
 * Hash结构效率高，那为什么索引结构要设计成树型呢?
 * 原因1: Hash 索引仅能满足(=) (<>) 和IN查询。
 *      如果进行范围查询，哈希型的索引，时间复杂度会退化为0(n);
 *      而树型的“有序特性，依然能够保持0(log2N)的高效率。
 * 原因2: Hash 索引还有一个缺陷，数据的存储是没有顺序的，
 *       在ORDER BY的情况下，使用Hash索引还需要对数据重新排序。
 * 原因3:对于联合索引的情况，Hash 值是将联合索引键合并后一起来计算的,
 *      无法对单独的一个键或者几个索引键进行查询。
 * 原因4:对于等值查询来说，通常Hash索引的效率更高，不过也存在-种情况，
 *      就是索引列的重复值如果很多，效率就会降低。
 *      这是因为遇到Hash冲突时,需要遍历桶中的行指针来进行比较,
 *      找到查询的关键字，非常耗时。所以, Hash 索引通常不会用到重复值多的列上，
 *      比如列为性别、年龄的情况等。
 * Hash索引存在着很多限制，相比之下在数据库中B+树索引的使用面会更广，
 * 不过也有一些场景采用Hash索引效率更高，
 * 比如在键值型(Key-Value) 数据库中，Redis 存储的核心就是Hash 表。
 * MySQL中的Memory存储弓|擎支持Hash存储,如果我们需要用到查询的临时表时，
 * 就可以选择Memory存储引擎,把某个字段设置为Hash索引,
 * 比如字符串类型的字段,进行Hash计算之后长度可以缩短到几个字节。
 * 当字段的重复度低，而且经常需要进行等值查询的时候，采用Hash索弓|是个不错的选择。
 *
 *
 * 另外，InnoDB本身不支持Hash索引，但是提供自适应Hash索引
 * 什么情况下才会使用自适应Hash索引呢?如果某个数据经常被访问，
 * 当满足一定条件的时候， 就会将这个数据页的地址存放到Hash表中。
 * 这样下次查询的时候，就可以直接找到这个页面的所在位置。
 * 这样让B+树也具备了Hash索引的优点。
 *
 */
